#include "SL.h"

void InitSL(SL* s)
{
	assert(s);
	s->arr = NULL;
	s->size = 0;
	s->capacity = 0;
}


void ExpandSL(SL* s)
{
	if (s->size == s->capacity)
	{
		size_t newcapacity = s->capacity == 0 ? 4 : 2 * s->capacity;
		T* newarr = (T*)realloc(s->arr, sizeof(T) * newcapacity);
		if (newarr == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		s->arr = newarr;
		s->capacity = newcapacity;
	}
}

void Push_BackSL(SL* s, T x)
{
	ExpandSL(s);
	s->arr[s->size++] = x;
}

void EraseSL(SL* s, size_t pos)
{
	assert(pos >= 0 && pos < s->size);
	size_t end = pos;
	while (end < s->size)
	{
		s->arr[end] = s->arr[end + 1];
		end++;
	}
	s->size--;
}

void PrintSL(SL* s)
{
	assert(s);
	for (size_t i = 0; i < s->size; i++)
	{
		printf("%d ", s->arr[i]);
	}
	printf("\n");
}

void InsertSort(T* a, size_t n)
{
	for (int i = 0;i < n - 1;i++)
	{
		int end = i;
		T tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

void SortSL(SL* s)
{
	assert(s);
	InsertSort(s->arr, s->size);
}

void DestroySL(SL* s)
{
	if (s->arr)
	{
		free(s->arr);
		s->arr = NULL;
	}
	s->size = 0;
	s->capacity = 0;
}

int FindSL(SL* s, T x)
{
	assert(s);
	for (size_t i = 0; i < s->size; i++)
	{
		if (x == s->arr[i])
		{
			return i;
		}
	}
	return -1;
}

//1  2    5    6 
void InsertSL(SL* s, size_t pos, T x)
{
	assert(s);
	assert(pos >= 0 && pos <= s->size);
	ExpandSL(&s);
	int end = s->size - 1;
	while (end >= (int)pos)
	{
		s->arr[end + 1] = s->arr[end];
		end--;
	}
	s->arr[pos] = x;
	s->size++;
}